0% completed
Problem Statement
Given a root of the binary tree, return an array containing nodes in its top view.
The top view of a binary tree consists of nodes that are visible when the tree is viewed from the top. If multiple nodes share the same horizontal distance from the root, only the first node encountered at that distance (in level order) is part of the top view.
Examples
Example 1
- Input: root =
[1, 2, 3, null, 5, 4, 6] - Expected Output:
[2, 1, 3, 6]
- Justification: It is a top view of the tree as shown in the diagram.
Example 2
- Input: root =
[1, 2, 3, 4, null, null, 7, 5, null, null, 8] - Expected Output:
[5, 4, 2, 1, 3, 7, 8]
- Justification: It is a top view of the tree as shown in the diagram.
Example 3
- Input: root =
[1, null, 2, 3, null, null, 4] - Expected Output:
[1, 2]
- Justification: It is a top view of the tree as shown in the diagram.
Solution
To solve this problem, we can use the Breadth-First Search (BFS) approach. This method explores each level of the tree and ensures that the first node encountered at each horizontal distance is captured. We maintain a horizontal distance for each node starting from the root (horizontal distance = 0) and update the view with the first node encountered at each distance.
This approach is efficient because BFS ensures that we process nodes level by level, and we can keep track of horizontal distances using a queue. Since we're only interested in the first node we encounter at each horizontal distance, BFS works perfectly for this case. We also maintain a hash map to store the top view nodes for each horizontal distance.
Step-by-step Algorithm
-
Check if the tree is empty:
- If the root is null, return an empty list since no top view is possible.
-
Create necessary data structures:
- Initialize an empty list
topViewNodesto store the result. - Use a
TreeMapcalledtopNodeMapto store the first node encountered at each horizontal distance. The key is the horizontal distance, and the value is the node value. - Use a
Queueto perform Breadth-First Search (BFS). The queue will store pairs of nodes and their respective horizontal distance from the root.
- Initialize an empty list
-
Add the root node to the queue:
- Insert the root node into the queue with a horizontal distance of
0.
- Insert the root node into the queue with a horizontal distance of
-
Start BFS traversal:
- While the queue is not empty, repeat steps 5 to 9:
-
Dequeue a node from the queue:
- Remove a node from the queue along with its horizontal distance.
-
Check if the horizontal distance is already in the map:
- If this horizontal distance is not in
topNodeMap, insert the current node’s value into the map with its horizontal distance as the key. - This ensures only the first node encountered at this horizontal distance is stored, as we are processing the tree level by level.
- If this horizontal distance is not in
-
Check if the current node has a left child:
- If the node has a left child, enqueue the left child with a horizontal distance of
current horizontal distance - 1.
- If the node has a left child, enqueue the left child with a horizontal distance of
-
Check if the current node has a right child:
- If the node has a right child, enqueue the right child with a horizontal distance of
current horizontal distance + 1.
- If the node has a right child, enqueue the right child with a horizontal distance of
-
Repeat the BFS traversal for all nodes:
- Continue until all nodes are processed in the BFS loop.
-
Extract the results:
- After the BFS completes, the
topNodeMapcontains the first node encountered at each horizontal distance. SinceTreeMapstores the keys in sorted order, iterate through the entries intopNodeMapand add the node values totopViewNodes.
- After the BFS completes, the
-
Return the result:
- Return the list
topViewNodescontaining the top view of the binary tree.
- Return the list
Algorithm Walkthrough
Input: [1, 2, 3, null, 5, 4, 6]
-
Initial Setup:
topViewNodes=[](empty list).topNodeMap={}(emptyTreeMap).queue=[(1, 0)](root node 1 with horizontal distance 0).
-
First BFS iteration:
- Dequeue
(1, 0): current node is 1, horizontal distance is 0. - Since horizontal distance 0 is not in
topNodeMap, add1to the map:topNodeMap = {0: 1}. - Enqueue the left child
2with horizontal distance-1:queue = [(2, -1)]. - Enqueue the right child
3with horizontal distance1:queue = [(2, -1), (3, 1)].
- Dequeue
-
Second BFS iteration:
- Dequeue
(2, -1): current node is 2, horizontal distance is-1. - Since horizontal distance
-1is not intopNodeMap, add2to the map:topNodeMap = {-1: 2, 0: 1}. - Node
2has no left child, so nothing is enqueued. - Enqueue the right child
5with horizontal distance0:queue = [(3, 1), (5, 0)].
- Dequeue
-
Third BFS iteration:
- Dequeue
(3, 1): current node is 3, horizontal distance is1. - Since horizontal distance
1is not intopNodeMap, add3to the map:topNodeMap = {-1: 2, 0: 1, 1: 3}. - Enqueue the left child
4with horizontal distance0:queue = [(5, 0), (4, 0)]. - Enqueue the right child
6with horizontal distance2:queue = [(5, 0), (4, 0), (6, 2)].
- Dequeue
-
Fourth BFS iteration:
- Dequeue
(5, 0): current node is 5, horizontal distance is0. - Since horizontal distance
0is already intopNodeMap, we do not update the map (only the first node at each distance is kept). - Node
5has no children, so nothing is enqueued.
- Dequeue
-
Fifth BFS iteration:
- Dequeue
(4, 0): current node is 4, horizontal distance is0. - Since horizontal distance
0is already intopNodeMap, we do not update the map. - Node
4has no children, so nothing is enqueued.
- Dequeue
-
Sixth BFS iteration:
- Dequeue
(6, 2): current node is 6, horizontal distance is2. - Since horizontal distance
2is not intopNodeMap, add6to the map:topNodeMap = {-1: 2, 0: 1, 1: 3, 2: 6}. - Node
6has no children, so nothing is enqueued.
- Dequeue
-
BFS completed:
- The
queueis now empty, so we exit the BFS loop.
- The
-
Extract the results:
- Iterate through
topNodeMapin order of horizontal distance:-1, 0, 1, 2. - Add the corresponding node values to
topViewNodes:[2, 1, 3, 6].
- Iterate through
-
Return the result:
- The final result is
topViewNodes = [2, 1, 3, 6].
Code
Complexity Analysis
Time Complexity
1. Level Order Traversal using Queue – :
- Every node in the tree is visited exactly once during the Breadth-First Search (BFS).
- For each node, we perform a constant amount of work (checking left/right children, calculating horizontal distance, etc.).
- So this part contributes
2. Storing values in TreeMap – per insertion:
- A
TreeMapis used to keep nodes sorted by horizontal distance. - Each
put()orcontainsKey()operation in aTreeMaptakes, where Kis the number of keys in the map. - In the worst case, you could have up to
Ndifferent horizontal distances → so each insertion/check could take up totime. - Over
Nnodes, the map operations costin total.
3. Collecting and returning results – :
- After BFS, you collect values from the
TreeMap, which takes.
Final Time Complexity:
- Queue traversal (BFS):
- TreeMap operations:
- Final result construction:
✅ So the overall time complexity is TreeMap for sorting horizontal distances.
Space Complexity
- The space complexity of the algorithm is
. This includes: - The queue used for BFS traversal, which in the worst case can contain
nodes. - The
TreeMapthat stores nodes at different horizontal distances. In the worst case, the tree can be completely skewed, which means the number of unique horizontal distances will also be.
- The queue used for BFS traversal, which in the worst case can contain
On this page
Problem Statement
Examples
Solution
Step-by-step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity
Space Complexity